This invention relates to quorum controlled asymmetric proxy cryptography for use in encrypting and decrypting transcripts.
Blaze et al. introduce the notion of proxy cryptography in M. Blaze, G. Bleumer, M. Strauss, xe2x80x9cAtomic Proxy Cryptography,xe2x80x9d EUROCRYPT ""98, pp. 127-144. In their model of proxy cryptography, there is an entityxe2x80x94the proxyxe2x80x94that can transform a transcript from being associated with a primary recipient to afterwards being associated with at least one secondary recipient. A xe2x80x9ctranscriptxe2x80x9d can be any type of electronic file that is sent from an originator to the primary recipient via a communications system. As a result, the transcript will have xe2x80x9cassociatedxe2x80x9d with it the primary recipient""s address that is used within the communications system. Examples of a transcript that it may be valuable to transform in this manner are E-mail messages, encryptions, identification proofs, and signatures. For E-mail messages and encryptions, the transcript may be transformed from an encryption using the proxy""s key to an encryption of the same message using the secondary recipient""s key; for identification proofs and signatures, the transcripts may be transformed from being associated with the originator, to instead being associated with the proxy. Blaze et al. define both symmetric and asymmetric proxy cryptography. For xe2x80x9csymmetric proxy cryptography,xe2x80x9d given the key used for transformation, the secret key of one party of the transformation can be derived from the secret key of the other. Conversely, in xe2x80x9casymmetric proxy cryptography,xe2x80x9d each party only needs to know his or her own secret key, or some transformation key derived from this. Therefore, asymmetric proxy cryptography is naturally better suited for many applications. However, while several symmetric constructions are provided by Blaze et al., there is merely a suggestion that asymmetric proxy cryptography exists.
Information is available on cryptographic techniques used in proactive security (for example, Y. Frankel, P. Gemmell, P. MacKenzie, M. Yung, xe2x80x9cProactive RSA,xe2x80x9d Proc. of CRYPTO ""97, pp. 440-454; A. Herzberg, S. Jarecki, H. Krawcyk, M. Yung, xe2x80x9cProactive Secret Sharing, or How to Cope with Perpetual Leakage,xe2x80x9d CRYPTO ""95, pp. 339-352; and A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, M. Yung, xe2x80x9cProactive Public Key and Signature Systems,xe2x80x9d Proceedings of the 4th ACM Conference on Computer and Communications Security, 1997, pp. 100-110), on methods for undeniable signatures (for example, D. Chaum, H. Van Antwerpen, xe2x80x9cUndeniable Signatures,xe2x80x9d CRYPTO ""89, pp. 212-216; and D. Chaum, xe2x80x9cZero-Knowledge Undeniable Signatures,xe2x80x9d EUROCRYPT ""90, pp. 458-464), Schnorr signatures (C. P. Schnorr, xe2x80x9cEfficient Signature Generation for Smart Cards,xe2x80x9d Advances in Cryptologyxe2x80x94Proceedings of CRYPTO ""89, pp. 239-252), methods for information-theoretical secret sharing (T. P. Pedersen, xe2x80x9cA threshold cryptosystem without a trusted party,xe2x80x9d D. W. Davies, editor, Advances in Cryptologyxe2x80x94EUROCRYPT ""91, volume 547 of Lecture Notes in Computer Science, pp. 522-526. Springer-Verlag, 1991), and mobile attackers (R. Ostrovsky and M. Yung, xe2x80x9cHow to withstand mobile virus attacks,xe2x80x9d Proceedings of the 10th ACM Symposium on the Principles of Distributed Computing, 1991, pp. 51-61.
Shamir introduces a (k,n) threshold scheme in A. Shamir, xe2x80x9cHow to Share a Secret,xe2x80x9d Communications of the ACM, Vol. 22, 1979, pp. 612-613. See also, T. P. Pedersen, EUROCRYPT ""91, pp. 522-526.
ElGamal introduces the ElGamal encryption algorithm in T. ElGamal, xe2x80x9cA Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,xe2x80x9d CRYPTO ""84, pp. 10-18.
Bellare et al. introduce methods that show how a non-interactive proof can be proven zero-knowledge in the random oracle model in M. Bellare, P. Rogaway, xe2x80x9cRandom Oracles are Practical: a paradigm for designing efficient protocols,xe2x80x9d 1st ACM Conference on Computer and Communications Security, pp. 62-73, 1993.
The shortcomings of existing E-mail systems are well known, for example, in one existing E-mail system incoming E-mail messages are protected with a public key encryption and sent directly to the primary recipient""s mailbox. A problem with this scheme arises when the primary recipient leaves or is absent for an extended period of time and E-mails sent to the primary recipient are needed. In this instance, the contents of the E-mails can not be accessed by any other users, unless they have the absent primary recipient""s secret key. Thus, the information contained in these E-mails, regardless of how urgently it is needed or vitally important it is to an organization is inaccessible until the primary recipient returns or his secret key is obtained.
Another existing E-mail system uses a single system administrator to distribute incoming E-mail messages to the intended primary recipients. This configuration can experience similar problems with those of the above described system if, for example, distribution of the E-mail is controlled by a single system administrator with the secret key and this system administrator leaves or is absent. In addition, in this system, the system administrator has total, unrestricted access to all E-mail messages in the system. While the problem of a missing system administrator can be overcome by having multiple E-mail system administrators (all of whom possess knowledge of the secret key), it multiplies the security problems by increasing the number of people who have unrestricted access to the E-mail system and, thus, makes confidential communications between parties less secure.
In another existing E-mail system, a group of system administrators are needed to distribute the E-mail. Incoming E-mail can be decrypted by the group of system administrators only if the entire group agrees and each uses their portion of the secret key to decrypt their associated portion of the E-mail message. Therefore, if an E-mail message in the primary recipient""s mailbox needs to be forwarded on, and the primary recipient is not available, all of the group of system administrators must decrypt their respective portions of the message, combine the results, and then forward the message to the necessary secondary recipients. A major problem with this system is that all of the system administrators must be available and once the decryption is finished, each system administrator in the group of system administrators has unrestricted access to the complete E-mail message.
Finally, in an existing symmetric proxy encryption system the proxy holds a key that allows him to transform the transcripts, but which also allows him to compute the secret key of the secondary recipient, given knowledge of the proxy""s own secret key. This, also, allows the secondary recipient to compute the secret key of the primary recipient or proxy server in a similar manner. This type of proxy encryption is disadvantageous in situations where there is no symmetric trust (or little trust at all). It also forces the participants to establish the shared transformation key ahead of time. The only advantage of a solution of this type appears to lie mainly in a potential improvement in efficiency, caused by the merging of the two decrypt and encrypt operations into one re-encryption operation performed during the transformation phase.
The above techniques and systems fail to provide effective and secure access to and forwarding of received transcripts from the primary recipient when the primary recipient is not available. Therefore, there is a need for a system and new techniques to provide asymmetric proxy cryptography for use in encrypting and decrypting transcripts.
My work extends the work of Blaze et al., that introduces the notion of proxy cryptography, demonstrates that symmetric proxy transformations exist, and conjectures that asymmetric proxy transformations also do exist. I demonstrate that asymmetric proxy transforms do indeed exist.
A proxy is an entity that is composed of one or more individuals called proxy servers. xe2x80x9cProxy serversxe2x80x9d perform the transformation of transcripts from being associated with a primary recipient to afterwards being associated with at least one secondary recipient. In one embodiment of the present invention, a quorum of proxy servers is selected from the available group of proxy servers to perform the transformation function. The xe2x80x9cquorum of proxy serversxe2x80x9d can consist of any and all non-empty subsets of proxy servers from the group of proxy servers. The exact membership of the quorum does not need to be identified until the time of the transformation, however, the minimum number of members in the quorum must be specified by the primary recipient before the secret key is shared among a quorum of the proxy servers. At the time of transformation, the system will dynamically allocate xe2x80x9csharesxe2x80x9d of the secret key to a quorum of the currently available proxy servers in the group of proxy servers based on the minimum number of required members specified by the primary recipient. For example, in a group of five (5) proxy servers, the primary recipient could specify that a minimum of three (3) proxy servers would constitute a quorum, and the secret key would be shared between these three proxy servers or, alternatively, the secret key could be shared between four or five proxy servers. While, in the present invention, the proxy is intended to consist of more than one proxy server, the present invention is still applicable to a single proxy server.
I focus on asymmetric proxy encryption, where for security, the transformation is performed under quorum control by a quorum of proxy servers. This guarantees that if there is not a dishonest quorum, then the plaintext message whose encryption is being transformed is not revealed to the proxy servers. My solution is efficient, allows tight control over actions (by the use of quorum cryptography), does not require any pre-computation phase to set up shared keys, and has a trust model appropriate for a variety of settings.
Consequently, my method and system for forwarding secret key-encrypted messages from a primary recipient to a secondary recipient, without disclosing the underlying encrypted message, solves the above-mentioned deficiencies in the prior art system. My method and system involves sharing portions of the secret key among a predetermined number of proxy servers and, upon receipt of an encrypted message by the proxy servers, each proxy server modifies the message by applying their individual share of the key portion to the encrypted message. The result of this modification is a message that is secret to the proxy servers but is decryptable by the secondary recipient.
There are two types of asymmetric proxy transformations. In the first, which is merely theoretical, the message of the initial encryption can be hidden from the proxy by not requiring the proxy to know the decryption key corresponding to the proxy""s own public key (but where the proxy is still able to perform the transformation). In the second, in which the proxy is distributed and all actions are quorum controlled, the message of the encryption is hidden from a xe2x80x9csufficiently honestxe2x80x9d proxy. The second, in which the control is held by a quorum of proxy servers, has efficient solutions and I elaborate on such an embodiment herein.
Such a mechanism is useful in many applications For example:
It allows the proxy to transform encrypted messages to encryptions with a variety of different recipient public keys, to allow for categorization of the encryptions. The categorization may be performed either as a function of the transcripts and their origins, randomly (for example, assigning an examiner to an electronically submitted patent), or as a function of time, and may be used to sort the encrypted messages according to priority or security clearance.
It allows more efficient communication to a large number of recipients that are physically clustered around the proxy; the sender would only need to send one encryption, along with an authenticated list of recipients. This may prove very useful for pay-tv, general multi-cast, and related applications.
It can be used for escrow encryption to separate the power of who can transform an encrypted message into a new transcript and who can read the plaintext message corresponding to such a transcript.
Last but not least, I believe that asymmetric proxy encryption may become a useful building block in the design of secure and efficient multi-party protocols.